1. Field of the Invention
The present invention relates to communication networks and, more particularly, to a method and apparatus for implementing multiple portals into an Rbridge network.
2. Description of the Related Art
Data communication networks may include various routers, switches, bridges, hubs, and other network devices coupled to and configured to pass data to one another. These devices will be referred to herein as “network elements.” Data is communicated through the data communication network by passing protocol data units, such as Internet Protocol (IP) packets, Ethernet Frames, data cells, segments, or other logical associations of bits/bytes of data, between the network elements by utilizing one or more communication links between the devices. A particular protocol data unit may be handled by multiple network elements and cross multiple communication links as it travels between its source and its destination over the network.
Network elements known as bridges are used to interconnect multiple physical links. Unless otherwise restricted, a bridge will broadcast traffic received on a particular link onto all other links to which it is attached. Where a group of bridges are interconnected, the links over which a particular bridge is allowed to broadcast traffic must be restricted to prevent loops from being formed in the bridged network. Specifically, if a loop is formed in the bridged network, a particular packet may continue to propagate around the loop, which will cause all network elements on the loop to continually broadcast the same packets. For example, FIG. 1 illustrates an example of a bridged network including bridges 1-8 that are connected by links 10-23. If a packet is received by node 1 from source S1 and is broadcast on the bridged network, node 1 would broadcast the packet on links 10, 11, and 13. Node 3, upon receipt, would broadcast the packet on links 12, 14, 15, & 16, which would cause node 2 to receive two copies of the packet. As the packet progressed further in the network additional copies of the packet would be generated causing further multiplication of the packet on the network.
One conventional way of determining which links should be used to broadcast packets by each bridge in a bridged network is to organize the links using a tree structure. Each of the nodes on the network will calculate where it fits into the tree and which of the available links on the network will be used to broadcast traffic on the network.
FIG. 2 illustrates one example of a type of tree that may be created to prevent loops in a bridged network. In the example shown in FIG. 2, a spanning tree is created to designate links between the nodes that will be used to broadcast traffic on the bridged network. In the illustrated embodiment, the spanning tree includes links 11, 12, 14, 15, 16, 21, and 22, and doesn't include the other links. When a packet is received by node 1 from source S1, it will broadcast the packet only on the links that are part of the spanning tree. Thus, node 1 will broadcast the packet on link 11 to node 3. Node 3 will broadcast the packet on links 12, 14, 15, and 16 (not on the link over which it was received), and the packet will progress through the spanning tree. Thus, using a spanning tree, a packet may be broadcast onto a bridged network and be delivered once to each node without causing packets to loop and the concomitant exponential proliferation of packets that looping may cause.
As shown in FIG. 2, the spanning tree provides a useful construct for allowing packets to be broadcast onto a bridge network. However, use of the spanning tree for unicast traffic may not be efficient, since the spanning tree concentrates all traffic onto a few of the links on the network, and may require traffic to take an indirect path between nodes. For example, assume that node 6 wanted to transmit data to node 4. If the data path were to follow the spanning tree, the data path would include link 21 from node 6 to node 8, link 15 from node 8 to node 3, and link 14 from node 3 to node 4. This three segment path may have a higher cost than the path through link 20 which extends directly between node 6 and node 4. Additionally, concentrating the traffic on the links forming the spanning tree may cause congestion on the links that form part of the spanning tree while allowing the other links to remain underutilized.
To solve this problem, routing bridges (Rbridges) have been developed. Rbridges are network elements that behave like bridges in connection with broadcasting traffic onto a network, but are able to route traffic through the network as well. In an Rbridge network, once a spanning tree has been established, such as in the example shown in FIG. 2, sources S1 and S2 will periodically broadcast a ping/hello message to allow the nodes 1 and 7 to learn about their respective attached sources. When one of the sources would like to communicate with the other source it will send an ARP request onto the network to determine the address of the intended destination. For example as shown in FIG. 3, assume that S1 needs to communicate with S2, and that S1 does not have S2's address. S1 will send an ARP broadcast to node 1, which will forward the ARP broadcast over the spanning tree on the Rbridge network (arrows 1-3) so that the ARP is received by all other nodes on the Rbridge network. As a result, all of the nodes on the network will know that S1 is located on node 1. Node 7 will receive the ARP request and forward the ARP request to S2 (arrow 4).
As shown in FIG. 4, S2 will generate a response to S1 with a unicast ARP response (arrow 5). The ARP response will be received by node 7 and forwarded to node 1, which will forward the ARP response to S1. Since the Rbridge network is able to route traffic, the ARP response may be sent directly to S1 using paths other than those forming the spanning tree. For example, the ARP response could take links 24, 20, and 13 to reach node 1. S1 and S2 may then compute routes to each other to enable point-to-point communications to occur over two unidirectional paths or over a bidirectional path on the network.
Rbridge networks are connected to external networks using portals. For example as shown in FIG. 5, one of the nodes (node 5 in this example) may be used as a portal to interconnect the Rbridge network with an external network. In this situation, a spanning tree may be established within the Rbridge network to handle broadcasts within the Rbridge network and a second spanning tree may be run on the external network outside of the Rbridge network. Traffic between the Rbridge network and the external network will be directed through the portal. Where there is only one portal, such as in the example shown in FIG. 5, the spanning tree within the Rbridge network and the spanning tree in the external network only connect at one point to prevent any possibility that a loop may be formed.
While a single portal Rbridge network architecture works well for relatively small Rbridge networks, as the Rbridge network grows it may be desirable to use multiple portals. Specifically, since the traffic between the Rbridge network and external network must pass through the portal to exit or enter the Rbridge network, the portal may become a bottleneck to the flow of traffic between the networks and also represents a single point of failure on the network.
If multiple portals are to be used on an Rbridge network, it becomes necessary to partition the spanning tree within the Rbridge network. Unfortunately, since a spanning tree will be computed from each portal, it is likely that the spanning trees may overlap, such that a particular node on the Rbridge network may be included on two or more trees which may cause loops to be formed in the network. Although it may be possible to calculate a set of balanced minimum spanning trees rooted at the portals, the computation of such trees is non-trivial. Particularly where the topography of the Rbridge network may change over time, recomputing new trees every time the network changes may be difficult to implement.